|
Finite Model Theory (FMT) is a subarea of model theory (MT). MT is the branch of mathematical logic which deals with the relation between a formal language (syntax) and its interpretations (semantics). FMT is a restriction of MT to interpretations of finite structures, which have a finite universe. * Since many central theorems of MT do not hold when restricted to finite structures, FMT is quite different from MT in its methods of proof. Central results of classical model theory that fail for finite structures include the compactness theorem, Gödel's completeness theorem, and the method of ultraproducts for first-order logic (FO). * As MT is closely related to mathematical algebra, FMT became an "unusually effective" instrument in computer science. In other words: "In the history of mathematical logic most interest has concentrated on infinite structures....Yet, the objects computers have and hold are always finite. To study computation we need a theory of finite structures." Thus the main application areas of FMT are: descriptive complexity theory, database theory and formal language theory. * FMT is mainly about discrimination of structures. The usual motivating question is whether a given class of structures can be described (up to isomorphism) in a given language. For instance, can all cyclic graphs be discriminated (from the non-cyclic ones) by a sentence of the first-order logic of graphs? This can also be phrased as: is the property "cyclic" FO expressible? ==Basic Challenges== A single structure can always be axiomatized in first-order logic, where axiomatized in a language L means described uniquely up to isomorphism by a single L-sentence. Some finite sets of structures can also be axiomatized in FO. However, FO is not sufficient to axiomatize any set containing infinite structures. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Finite model theory」の詳細全文を読む スポンサード リンク
|